COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00008 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\rm
\line{\sevenrm a10.tex[162,phy] \today\hfill}

\parskip 5pt
\bigskip
\line{\bf Multidimensional Summation\hfill}

We write $\sum↓{a,b}P(a,b):f(a,b)$ to mean the sum of $f(a,b)$ over
integer values satisfying the predicate $P(a,b)$. An identity reducing
multidimensional summation to iterated unidimensional summation is
$$\sum↓{a,b}P(a,b):f(a,b)=\sum↓a\exists b.P(a,b):\sum↓bP(a,b):f(a,b)\,.$$
If the summand is a function of $a$ alone,
$$\eqalign{\sum↓{a,b}P(a,b):f(a)&=\sum↓a\exists b.P(a,b):f(a)\sum↓bP(a,b):1\cr
\noalign{\smallskip}
&=\sum↓a\exists b.P(a,b):f(a)\bigl({\rm \#} b\mid P(a,b)\bigr)\,.\cr}$$

\smallskip
\disleft 38pt::{\bf Example:}

$$\sum↓{a,b}1≤a≤b≤n:a↑2=\sum↓a 1≤a≤n:a↑2(n-a+1)\,.$$

\smallskip
If $f$ is a function of $a+g(b)$, introduce a new variable $c=a+g(b)$,
$a=c-g(b)$. Then
$$\eqalign{\sum↓{a,b}P(a,b):f\bigl(a+g(b)\bigr)&=\sum↓{b,c}P\bigl(c-g(b),b\bigr):
f(c)\cr
\noalign{\smallskip}
&=\sum↓c\exists b.P\bigl(c-g(v),b\bigr):\sum↓bP\bigl(c-g(v),b\bigr):f(c)\cr
\noalign{\smallskip}
&=\sum↓b\exists b.P\bigl(c-g(b),b\bigr):f(c)\bigl({\rm \#}b\mid 
P\bigl(c-g(b),b\bigr)\bigr)\,.\cr}$$
Typically, $P$ is a set of linear inequalities, and $g$ is linear. An
existentially quantified variable can be removed from a set of linear
inequalities on integer expressions by these stages:

\smallskip
\disleft 25pt:(1):
Replace $x<y$ by $x+1≤y$, $x>y$ by $x≥y+1$.

\smallskip
\disleft 25pt:(2):
If $b$ is the existentially quantified variable, put each inequality in
one of the forms $x↓i≤b$, $b≤y↓j$, or $z↓k≥0$, where the $x$'s, $y$'s,
and~$z$'s do not contain~$b$. Then the set of relations becomes
$x↓i≤y↓j$, $z↓k≥0$ for all $i,j,k$.

\smallskip
\disleft 25pt:(3):
The number of values of $b$ satisfying such a relation, for the region
$z↓k≥0$, is the number of values in the range
$\bigl(\max(x↓i),\min(y↓j)\bigr)$, or
$\min(y↓j)+1\dminus \max(x↓i)$; equivalently, $\min(y↓j+1\dminus x↓i)$.

If $x↓i$ and $y↓j$ are not integral, use $\lceil x↓i\rceil$ and $\lfloor 
y↓j\rfloor$.

\vfill\eject

\disleft 38pt::{\bf Example:}

$$\eqalign{\sum↓{a,b}&1≤\{a,b\}≤n:{1\over a+b}\cr
\noalign{\smallskip}
&=\sum↓{a,s}1≤\{a,s-a\}≤n:{1\over s}\cr
\noalign{\smallskip}
&=\sum↓s2≤s≤2n:{1\over s}\cdot \bigl(\# a\mid \max(1,s-n)≤a≤\min(n,s-1)\bigr)\cr
\noalign{\smallskip}
&=\sum↓s2≤s≤n+1:{1\over s}(\# a\mid 1≤a≤s-1)\cr
\noalign{\smallskip}
&\qquad +\sum↓sn+2≤s≤2n:{1\over s}(\# a\mid s-n≤a≤n)\cr
\noalign{\smallskip}
&=\sum↓s2≤s≤n+1:{s-1\over s}+\sum↓sn+2≤s≤2n:{2n+1-s\over s}\cr
\noalign{\smallskip}
&=n-(H↓{n+1}-1)+(2n+1)(H↓{2n}-H↓{n+1})-(n-1)\cr
\noalign{\smallskip}
&=(2n+1)H↓{2n}-(2n+2)H↓{n+1}+2\cr
\noalign{\smallskip}
&=(2n+1)H↓{2n}-(2n+2)H↓n\,.\cr}$$

\disleft 38pt::{\bf Example:}
Assume $c≥1$. Find 
$$s=\sum↓{a,b}m≤a≤b≤n:{1\over b-a+c}\,.$$ 
Define
$$\displaylines{d=b-a+c\,;\cr
\noalign{\smallskip}
s=\sum↓{a,d}m≤a≤a+d-c≤n:{1\over d}\,;\cr
\noalign{\smallskip}
\exists a.m≤a≤a+d-c≤n≡c≤d∧m≤n-d+c≡c≤d≤n-m+c\,;\cr
\noalign{\smallskip}
(\# a|m≤a≤n-d+c)={n-m-d+c+1\over d}\,;\cr}$$
$$\eqalign{s&=\sum↓dc≤d≤n-m+c:{n-m-d+c+1\over d}\cr
\noalign{\smallskip}
&=(n-m+c+1)(H↓{n-m+c}-H↓{c-1})-(\# d\mid c≤d≤n-m+c)\cr
\noalign{\smallskip}
&=(n-m+c+1)(H↓{n-m+c}-H↓{c-1})-(n-m+1)\,.\cr}$$
This result is useful in analyzing Quicksort and its relatives.


\bigskip
\parindent0pt
\copyright 1986 Robert W. Floyd.
First draft (not published)
June 23, 1986.
%revised date;
%subsequently revised.

\bye